package binary_search

/*
查找递增序列arr里面距离最近等于k的数的下标;
没找到返回-1
*/
func BinarySearchIncreseEqualClosest(s, e int, arr []int, k int) int {
	if s > e {
		return -1
	}
	if s == e {
		if arr[s] == k {
			return s
		}
	}
	if s+1 == e {
		if arr[s] == k {
			return s
		}
		if arr[e] == k {
			return e
		}
		return -1
	}
	c := s + (e-s)/2
	if arr[c] > k {
		return BinarySearchIncreseEqualClosest(s, c-1, arr, k)
	}
	if arr[c] == k {
		result := BinarySearchIncreseEqualClosest(s, c-1, arr, k)
		if result != -1 {
			return result
		}
		return c
	}
	return BinarySearchIncreseEqualClosest(c+1, e, arr, k)
}

/*
查找递增序列arr里面距离最远等于k的数的下标;
没找到返回-1
*/
func BinarySearchIncreseEqualFarthest(s, e int, arr []int, k int) int {
	if s > e {
		return -1
	}
	if s == e {
		if arr[s] == k {
			return s
		}
	}
	if s+1 == e {
		if arr[s] == k {
			return s
		}
		if arr[e] == k {
			return e
		}
		return -1
	}
	c := s + (e-s)/2
	if arr[c] > k {
		return BinarySearchIncreseEqualFarthest(s, c-1, arr, k)
	}
	if arr[c] == k {
		result := BinarySearchIncreseEqualFarthest(c+1, e, arr, k)
		if result != -1 {
			return result
		}
		return c
	}
	return BinarySearchIncreseEqualFarthest(c+1, e, arr, k)
}

/*
查找递减序列arr里面距离最远等于k的数的下标;
没找到返回-1
*/
func BinarySearchDecreseEqualFarthest(s, e int, arr []int, k int) int {
	if s > e {
		return -1
	}
	if s == e {
		if arr[s] == k {
			return s
		}
		return -1
	}
	if s+1 == e {
		if arr[e] == k {
			return e
		}
		if arr[s] == k {
			return s
		}
		return -1
	}
	c := s + (e-s)/2
	if arr[c] > k {
		return BinarySearchDecreseEqualFarthest(c+1, e, arr, k)
	}
	if arr[c] == k {
		result := BinarySearchDecreseEqualFarthest(c+1, e, arr, k)
		if result != -1 {
			return result
		}
		return c
	}
	return BinarySearchDecreseEqualFarthest(s, c-1, arr, k)
}

/*
查找递减序列arr里面距离最近等于k的数的下标;
没找到返回-1
*/
func BinarySearchDecreseEqualClosest(s, e int, arr []int, k int) int {
	if s > e {
		return -1
	}
	if s == e {
		if arr[s] == k {
			return s
		}
	}
	if s+1 == e {
		if arr[s] == k {
			return s
		}
		if arr[e] == k {
			return e
		}
		return -1
	}
	c := s + (e-s)/2
	if arr[c] > k {
		return BinarySearchDecreseEqualClosest(c+1, e, arr, k)
	}
	if arr[c] == k {
		result := BinarySearchDecreseEqualClosest(s, c-1, arr, k)
		if result != -1 {
			return result
		}
		return c
	}
	return BinarySearchDecreseEqualClosest(s, c-1, arr, k)
}

/*
arr是单调递增
在sorted arr数组中下标范围[s,e]中查找满足这样的下标i
arr[i]<=k<arr[i+1]
没有就返回-1
*/
func BinarySearchIncreaseSmallClosest(s, e int, arr []int, k int) int {
	if s > e || len(arr) < 1 {
		return -1
	}
	if s == e {
		if arr[s] <= k {
			return s
		}
		return -1
	}
	if s+1 == e {
		if arr[e] <= k {
			return e
		}
		if arr[s] <= k {
			return s
		}
		return -1
	}
	c := (e-s)/2 + s
	if arr[c] < k {
		return BinarySearchIncreaseSmallClosest(c, e, arr, k)
	}
	if arr[c] == k {
		cOther := BinarySearchIncreseEqualClosest(s, c-1, arr, k)
		if cOther != -1 {
			return cOther
		}
		return c
	}
	return BinarySearchIncreaseSmallClosest(s, c-1, arr, k)
}

/*
arr是单调递增
在sorted arr数组中下标范围[s,e]中查找满足这样的下标i
arr[i-1]<k<=arr[i]
没有就返回-1
*/
func BinarySearchIncreaseBig(s, e int, arr []int, k int) int {
	if s > e || len(arr) < 1 {
		return -1
	}
	if s == e {
		if arr[s] >= k {
			return s
		}
	}
	if s+1 == e {
		if arr[s] >= k {
			return s
		}
		if arr[e] >= k {
			return e
		}
		return -1
	}
	c := (e-s)/2 + s
	if arr[c] > k {
		return BinarySearchIncreaseBig(s, c, arr, k)
	}
	if arr[c] == k {
		cOther := BinarySearchIncreseEqualClosest(s, c-1, arr, k)
		if cOther != -1 {
			return cOther
		}
		return c
	}
	return BinarySearchIncreaseBig(c+1, e, arr, k)
}

/*
arr是单调递减
在sorted arr数组中下标范围[s,e]中查找查找满足这样的下标i
arr[i]<=k<arr[i-1]
没有就返回-1
*/
func BinarySearchDecreaseSmall(s, e int, arr []int, k int) int {
	if s > e || len(arr) < 1 {
		return -1
	}
	if s == e {
		if arr[s] <= k {
			return s
		}
		return -1
	}
	if s+1 == e {
		if arr[s] <= k {
			return s
		}
		if arr[e] <= k {
			return e
		}
		return -1
	}
	c := (e-s)/2 + s
	if arr[c] > k {
		return BinarySearchDecreaseSmall(c+1, e, arr, k)
	}
	//有可能c的前面还有==k的需要再处理下
	if arr[c] == k {
		cOther := BinarySearchDecreseEqualClosest(s, c-1, arr, k)
		if cOther != -1 {
			return cOther
		}
		return c
	}
	return BinarySearchDecreaseSmall(s, c, arr, k)
}

/*
arr是单调递减
在sorted arr数组中下标范围[s,e]中查找查找满足这样的下标i
arr[i+1]<k<=arr[i]
*/
func BinarySearchDecreaseBig(s, e int, arr []int, k int) int {
	if s > e || len(arr) < 1 {
		return -1
	}
	if s == e {
		if arr[s] >= k {
			return s
		}
		return -1
	}
	if s+1 == e {
		if arr[e] >= k {
			return e
		}
		if arr[s] >= k {
			return s
		}
		return -1
	}
	c := (e-s)/2 + s
	if arr[c] > k {
		return BinarySearchDecreaseBig(c, e, arr, k)
	}
	if arr[c] == k {
		cOther := BinarySearchDecreseEqualFarthest(c+1, e, arr, k)
		if cOther != -1 {
			return cOther
		}
		return c
	}
	return BinarySearchDecreaseBig(s, c-1, arr, k)
}
